package com.duoduo.剑指Offer;

/**
 * @program: algorithm
 * @description: 在排序数组中查找数字08
 * 统计一个数字在排序数组中出现的次数。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *
 * @author: chaidl  ！
 * @create: 2022-05-23 00:03
 */
public class 在排序数组中查找数字08 {
	public int search(int[] nums, int target) {
	//	找到第一个target出现的位置
		int first=findFirst(nums,target);
		int end=findEnd(nums,target);
		if (first==-1 && end==-1){
			return 0;
		}
		if (first==-1 || end == -1){
			return 1;
		}
		return end-first+1;
	}
	
	private int findEnd(int[] nums, int target) {
		//5,7,7,8,8,10
		//0 1 2 3 4 5
		//采用双指针
		//2 2
		//0 1
		int left=0,right = nums.length-1;
		while (left<=right) {
			int mid=(left + right) /2;
			if (nums[mid] == target){
				//	如果中间的树刚好是目标值，则判断他的左边是否为空或者左边数的大小
				if (mid== nums.length-1  || nums[mid+1]>target){
					return mid;
				}
				left=mid+1;
			}else if (nums[mid] <target){
				left=mid+1;
			}else if (nums[mid] > target){
				right=mid - 1;
			}
		}
		return -1;
	}
	
	private int findFirst(int[] nums, int target) {
		//5,7,7,8,8,10
		//0 1 2 3 4 5
		//2 2
		//0 1
		//采用双指针
		int left=0,right = nums.length-1;
		while (left<=right) {
		    int mid=(left + right) /2;
			if (nums[mid] == target){
			//	如果中间的树刚好是目标值，则判断他的左边是否为空或者左边数的大小
				if (mid==0 || nums[mid-1]<target){
					return mid;
				}
				right=mid-1;
			}else if (nums[mid] <target){
				left=mid+1;
			}else if (nums[mid] > target){
				right=mid - 1;
			}
		}
		return -1;
	}
}
